package demo3;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n + 1];
        for(int i = 0; i <= n; i++) { dp[i] = 1;}

        int ret = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j < i; j++){
                if(nums[i - 1] - nums[j - 1] > 0){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;

        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 0; i < n; i++) {
            f[0] = g[0] = 1;
        }

        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    f[i] = Math.max(g[j] + 1, f[i]);
                }else if(nums[i] < nums[j]){
                    g[i] = Math.max(f[j] + 1, g[i]);
                }
            }
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }


    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;

        int[] count = new int[n];
        int[] len = new int[n];
        for(int i = 0; i < n; i++){
            count[i] = 1;
            len[i] = 1;
        }

        int retcount = 1, retlen = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(len[j] + 1 == len[i]){
                        count[i] += count[j];
                    }else if(len[j] + 1 > len[i]){
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            if(retlen == len[i]){
                retcount += count[i];
            }else if(retlen < len[i]){
                retlen = len[i];
                retcount = count[i];
            }
        }
        return retcount;
    }


    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b ) -> a[0] - b[0]);
        int n = pairs.length;

        int[] dp = new int[n];
        for(int i = 0; i < n; i++) { dp[i] = 1;}

        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(pairs[i][0] > pairs[j][1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }


    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> hash = new HashMap<>();

        int ret = 1;
        for(int x : arr){
            hash.put(x, hash.getOrDefault(x - difference, 0) + 1);
            ret = Math.max(ret, hash.get(x));
        }
        return ret;
    }


    public int lenLongestFibSubseq(int[] arr) {
        //将 数组中的元素 + 下标 绑定，扔到哈希表里
        Map<Integer, Integer> hash = new HashMap<>();
        int n = arr.length;
        for(int i = 0; i < n; i++) { hash.put(arr[i], i);}

        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = 2;
            }
        }

        int ret = 2;
        for(int j = 2; j < n; j++){  //固定最后一个数
            for(int i = 1; i < j; i++){  //枚举倒数第二个数
                int a = arr[j] - arr[i];
                if(a < arr[i] && hash.containsKey(a)){
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                }
                ret = Math.max(ret, dp[i][j]);
            }
        }
        return ret < 3 ? 0 : ret;
    }
}
